[2주차 Stack & Hash] 운송트럭 - Lv1

문제 설명

XX 회사는 트럭을 이용해 상품을 운반합니다. 트럭은 최대 무게가 한정되어있습니다. 직원은 트럭에 상품을 순서대로 실으며, 상품을 실을 수 없는 트럭은 바로 목적지로 출발합니다. 이때 우리는 모든 상품을 운반하는데 필요한 트럭은 최소 몇 대인지 구하려 합니다.

예를 들어, 각 상품의 스펙이 다음과 같고, 트럭의 허용 무게가 300, 실어야 할 상품이 [toy, snack, snack]라고 합니다.

이 경우 첫째 상품과 둘째 상품은 같은 트럭에 들어가지만, 셋째 상품은 다른 트럭에 넣어야 합니다. 따라서 필요한 트럭 수는 두 대 입니다.

트럭의 허용 무게 max_weight와 상품의 스펙을 담은 배열 specs, 운반할 상품의 이름이 순서대로 들은 배열 names가 주어집니다. 이때, 상품을 순서대로 운반하기 위해 필요한 트럭 수를 리턴하는 함수, soution을 완성하세요.

제한 조건

• max_weight는 1 이상 100,000 이하입니다.

• specs의 길이는 1 이상 100,000 이하입니다.

  • specs의 원소는 [상품 이름, 상품 무게]를 나타냅니다.
  • 상품 이름은 길이가 1 이상 10,000 이하인 문자열입니다.
  • 상품 무게는 1 이상 max_weight 이하인 자연수를 나타내는 문자열입니다.
  • 이름이 같은 상품은 없습니다.

• names는 길이가 1 이상 10,000 이하인 배열입니다.

  • names의 원소는 모두 specs에 있는 상품입니다.

입출력 예

입출력 예 설명

입출력 예 #1

앞서 설명한 예와 같습니다.

입출력 예 #2

모든 상품은 각각 다른 트럭에 들어갑니다. 두 번째 트럭을 호출하면 첫 번째 트럭은 목적지로 출발하므로, 세 번째 상품을 첫 번째 트럭에 넣을 수는 없습니다.

나의 풀이

첫번째 풀이

소스

def solution(max_weight, specs, names):
    answer = 0
    sum_weight = 0

    spec_dict = {}
    for spec in specs:
        spec_dict[spec[0]] = int(spec[1])

    for name in names:
        sum_weight += spec_dict[name]

        if sum_weight > max_weight:
            sum_weight = spec_dict[name]
            answer += 1

    if sum_weight > 0:
        answer += 1

    return answer

설명

• 해당 문제는 hash 즉, python의 dictionary를 이용하면 쉽게 풀 수 있다.
• 각 상품의 가격을 바로 찾을 수 있게 하는 것이 핵심 아이디어.
• names를 순회하면서 용량이 초과하면 개수를 더하는 방식이다.

결과

통과

리뷰

• spec_dict = dict(specs)로 줄일 수 있습니다. :) 단 int로 변환되지는 않습니다.
• 무조건 1대는 있기 때문에 최초에 answer = 1로 초기화하면 후처리가 없어도 괜찮습니다. :)

두번째 풀이

소스

def solution(max_weight, specs, names):
    answer = 1
    specs = dict(specs)
    sum_weight = 0

    for name in names:
        weight = int(specs[name])
        sum_weight += weight
        if sum_weight > max_weight:
            sum_weight = weight
            answer += 1

    return answer

설명

• 리뷰 반영
• 코드량이 줄었다.

결과

통과